﻿using System;
using System.Collections.Generic;
using System.Text;

namespace MLForgeSharp.Models.SupervisedLearningModels.EnsembleLearning.Bagging
{
    /// <summary>
    /// 孤立森林
    /// </summary>
    public class IsolationForest
    {
        private class IsolationTree
        {
            public int SplitFeature { get; set; } // 分裂特征
            public double SplitValue { get; set; } // 分裂值
            public IsolationTree LeftChild { get; set; } // 左子节点
            public IsolationTree RightChild { get; set; } // 右子节点
            public int Size { get; set; } // 节点大小
        }

        private List<IsolationTree> forest; // 孤立森林
        private int numTrees; // 树的数量
        private int subSamplingSize; // 子采样大小
        private Random random;

        public IsolationForest(int numTrees = 100, int subSamplingSize = 256)
        {
            this.numTrees = numTrees;
            this.subSamplingSize = subSamplingSize;
            this.forest = new List<IsolationTree>();
            this.random = new Random();
        }

        // 构建孤立树
        private IsolationTree BuildIsolationTree(double[][] data, int currentHeight, int maxHeight)
        {
            if (data.Length <= 1 || currentHeight >= maxHeight)
            {
                return new IsolationTree { Size = data.Length };
            }

            int featureIndex = random.Next(data[0].Length);
            double minValue = data[0][featureIndex];
            double maxValue = data[0][featureIndex];
            for (int i = 1; i < data.Length; i++)
            {
                if (data[i][featureIndex] < minValue) minValue = data[i][featureIndex];
                if (data[i][featureIndex] > maxValue) maxValue = data[i][featureIndex];
            }

            double splitValue = minValue + (maxValue - minValue) * random.NextDouble();

            List<double[]> leftData = new List<double[]>();
            List<double[]> rightData = new List<double[]>();
            foreach (double[] point in data)
            {
                if (point[featureIndex] < splitValue)
                {
                    leftData.Add(point);
                }
                else
                {
                    rightData.Add(point);
                }
            }

            return new IsolationTree
            {
                SplitFeature = featureIndex,
                SplitValue = splitValue,
                LeftChild = BuildIsolationTree(leftData.ToArray(), currentHeight + 1, maxHeight),
                RightChild = BuildIsolationTree(rightData.ToArray(), currentHeight + 1, maxHeight),
                Size = data.Length
            };
        }

        // 计算路径长度
        private double PathLength(double[] point, IsolationTree tree, int currentPathLength)
        {
            if (tree.LeftChild == null && tree.RightChild == null)
            {
                if (tree.Size <= 1)
                {
                    return currentPathLength;
                }
                else
                {
                    return currentPathLength + 2 * (Math.Log(tree.Size - 1) + 0.5772156649) - 2 * (tree.Size - 1) / tree.Size;
                }
            }

            if (point[tree.SplitFeature] < tree.SplitValue)
            {
                return PathLength(point, tree.LeftChild, currentPathLength + 1);
            }
            else
            {
                return PathLength(point, tree.RightChild, currentPathLength + 1);
            }
        }

        // 训练模型
        public void Train(double[][] data)
        {
            int maxHeight = (int)Math.Ceiling(Math.Log(subSamplingSize, 2));
            for (int i = 0; i < numTrees; i++)
            {
                double[][] subSample = new double[subSamplingSize][];
                for (int j = 0; j < subSamplingSize; j++)
                {
                    subSample[j] = data[random.Next(data.Length)];
                }
                forest.Add(BuildIsolationTree(subSample, 0, maxHeight));
            }
        }

        // 计算异常评分
        public double AnomalyScore(double[] point)
        {
            double avgPathLength = 0.0;
            foreach (IsolationTree tree in forest)
            {
                avgPathLength += PathLength(point, tree, 0);
            }
            avgPathLength /= numTrees;

            return Math.Pow(2, -avgPathLength / (2 * (Math.Log(subSamplingSize - 1) + 0.5772156649)));
        }
    }

    // 示例程序
    public class IsolationForestExample
    {
        public IsolationForestExample()
        {
            // 示例数据
            double[][] data = new double[][]
        {
            new double[] { 1.0, 2.0 },
            new double[] { 1.1, 2.1 },
            new double[] { 1.2, 2.2 },
            new double[] { 1.3, 2.3 },
            new double[] { 10.0, 10.0 }, // 异常点
            new double[] { 10.1, 10.1 }  // 异常点
        };

            // 创建模型
            IsolationForest model = new IsolationForest(numTrees: 100, subSamplingSize: 4);

            // 训练模型
            model.Train(data);

            // 计算异常评分
            double[] testPoint = { 10.0, 10.0 };
            double anomalyScore = model.AnomalyScore(testPoint);

            System.Console.WriteLine("异常评分: " + anomalyScore);
        }
    }
}
